#include <iostream>
#include <cstring>

using namespace std;

// problem 5
void print_parentheses_rec(ostream& os, size_t left, size_t right, char* output, size_t pos);

void print_parentheses(ostream& os, size_t n) {
  char* output = new char[2*n+1];
  memset(output, '\0', 2*n+1);
  print_parentheses_rec(os, n, n, output, 0);
}

void print_parentheses_rec(ostream& os, size_t left, size_t right, char* output, size_t pos) {
  if (right == 0) {
    os << output << endl;
    return;
  }

  if (left > 0) {
    output[pos] = '(';
    print_parentheses_rec(os, left-1, right, output, pos+1);
    output[pos] = '\0';
  }

  if (left < right) {
    output[pos] = ')';
    print_parentheses_rec(os, left, right-1, output, pos+1);
    output[pos] = '\0';
  }
}

// problem 7
size_t next_demonsion(size_t d) {
  if (d == 25) 
    return 10;
  if (d == 10) 
    return 5;
  if (d == 5)
    return 1;
  else 
    throw "No more dimensions";
}

size_t make_change(size_t n, size_t dem) {
  if (n == 0) return 1;
  if (dem == 1) return 1;

  size_t ways = 0;
  for (size_t i = 0; i * dem <= n; i++) {
    ways += make_change(n - i*dem, next_demonsion(dem));
  }
  return ways;
}

int main() {
  cout << "Test problem 5: print parentheses" << endl;
  print_parentheses(cout, 3);
  cout << endl;

  cout << "Test problem 7: make change" << endl;
  size_t n = 10;
  cout << "ways to break " << n << " cents is " << make_change(n, 25) << endl;

  return 0;
}
